Category

MA

P21

Reformulating the Newton Direction Computation as a Least Squares

Problem

Abstract

From robust data fitting in statistics to L1 finite element methods

for fluid dynamics, the overdetermined L1 minimization problem arises

in many practical applications. First, this paper presents a proof of the

convergence of Newton's method for the smoothed overdetermined L1

minimization problem. Next, new formulas are derived for computing

the Newton search direction by solving a linear least squares problem.

Numerical examples show that the new least squares reformulation

stably computes L1 minimizers for coefficient matrices with condition

numbers from 10^3 to 10^6. In contrast, the existing normal equations

formulation completely failed to provide an accurate solution for

the ill-conditioned coefficient matrices with condition numbers of 10^5

and 10^6. The reformulation currently holds great potential for any

overdetermined ill-conditioned L1 minimization problem and can be

easily extended to nonlinear or underdetermined problems. This paper

presents many practical applications and the circumstances where

ill-conditioned matrices appear.

Bibliography

P. B. Bochev and M. D. Gunzburger, Least-Squares Finite Element

Methods, Springer, New York, NY, 1 ed., 2009.

E. J. Cands, M. Rudelson, T. Tao, and R. Vershynin, Error

correction via linear programming, in Proceedings of the 46th Annual

IEEE Symposium on Foundations of Computer Science, IEEE, 2005.

J. Demmel, Applied Numerical Linear Algebra, Siam, Philidelphia, 1 ed.,

1997.

M. S. Gockenbach, Newton's method for unconstrained minimization.

http://www.math.mtu.edu/~msgocken/ma5630spring2003/lectures/newton

/newton/node5.html, January 2003.

J. L. Guermond, A finite element technique for solving first-order

PDEs in LP , SIAM Journal of Numerical Analysis, 42 (2004), pp. 714-737.

First Previous Next Last